from typing import List


class Solution:
    def dfs(self, num, ans, n):
        if num > n:
            return
        ans.append(num)
        for i in range(10):
            self.dfs(num * 10 + i, ans, n)

    def lexicalOrder(self, n: int) -> List[int]:
        ans = []
        for i in range(1, 10):
            self.dfs(i, ans, n)
        return ans

    def lexicalOrder2(self, n: int) -> List[int]:
        '''
        使用自带的sorted函数支持字典序排序
        '''
        return sorted(range(1, n+1), key=str)